#include<stdio.h>
/*
 * 小球称重问题：假设有n（n>1)个小球，其中有1个小球的重量比其他的都稍重，给你一个天平，请问最多需要多少次可以定位稍重的小球？最少多少次？
 * 小球个数   最少次数   最多次数
 * 2          1          1
 * 3          1          1
 * 4          2          2
 * 5          1          2
 * 6          2          2
 * 7          1          2
 * 8          3          3
 * 9          1          3
 * 10         2          3
 * 11         1          3
 * 12         3          3
 * 13         1          3
 * 14         2          3
 * 15         1          3
 * 16         4          4
 * 17         1          4
 * 18         2          4
 * 19         1          4
 * 20         3          4
 * 规律：
 * 当小球个数为N时：
 * 1、最少次数，当N为奇数时，最少次数恒为1，这是最凑巧的情形；当N为偶数时，最少次数等于小球个数为 N/2 时的最少次数+1；
 * 2、最多次数, 当N为奇数和为偶数时，都是为 N/2 时的最多次数+1；
 *
 * 总结：
 * 1、递归问题的关键在于明确2个因子，一是谁是变化的量(本例为小球个数), 二是当变化的量取值为N时与取其他相关值(N-1,N/2,N/r等等)有什么关联(注意一般是与N之前的值进行比较，找出两者的关系表达式);
 * 2、确定第2个关键因子一时看不出来时，可以按数学上的从特殊到一般的方法进行寻找，先取其前10，20个值，观察并抽象出其规律，然后再回归一般情形；
 * 3、第一个关键因子也不一定是一个简单的变量，也可能是一个表达式，包含多个变量，比如二分查找里的：low <= high , 但是表达式内部的变量一定变化着的，一定会有low > high 出现，否则递归无法结束，变成死循环了。
 */

/*求最少次数*/
int least(int count){
	if(count==2 || count==3){
		return 1;
	}
	int ret = 0;
	if(count%2==0){
		return least(count/2) + 1;
	}else{
		return 1;
	}

	return 0;
}

/*求最多次数*/
int most(int count){
	if(count==2 || count==3){
        return 1;
    }
    return most(count/2) + 1;
}


int main()
{
	printf("请输入小球个数:\n");
	int count = 0;
	scanf("%d", &count);

	printf("最少次数:%d\n", least(count));
	printf("最多次数:%d\n", most(count));
	
	return 0;
}
